Circle plots demo

source('source.R')

Floyd-Warshall

Setup

n <- 6
blocksize <- 1
a <- circle_graph(n)
plotg(a)

Iterations

for (it in 1:n) {
  inds <- (blocksize * (it-1) + 1):(blocksize * it)
  a_new <- a
  a_new[inds, inds] <- fw(a[inds, inds, drop = FALSE])
  a_new <- minplus(a[, inds, drop = FALSE], a[inds, , drop = FALSE], a)
  plotg(a, inds = inds)
  plotl(a, a_new)
  a <- a_new
  title(paste("Iteration", it))
  print(a)
}

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1  Inf  Inf  Inf    1
## [2,]    1    0    1  Inf  Inf    2
## [3,]  Inf    1    0    1  Inf  Inf
## [4,]  Inf  Inf    1    0    1  Inf
## [5,]  Inf  Inf  Inf    1    0    1
## [6,]    1    2  Inf  Inf    1    0

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    2  Inf  Inf    1
## [2,]    1    0    1  Inf  Inf    2
## [3,]    2    1    0    1  Inf    3
## [4,]  Inf  Inf    1    0    1  Inf
## [5,]  Inf  Inf  Inf    1    0    1
## [6,]    1    2    3  Inf    1    0

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    2    3  Inf    1
## [2,]    1    0    1    2  Inf    2
## [3,]    2    1    0    1  Inf    3
## [4,]    3    2    1    0    1    4
## [5,]  Inf  Inf  Inf    1    0    1
## [6,]    1    2    3    4    1    0

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    2    3    4    1
## [2,]    1    0    1    2    3    2
## [3,]    2    1    0    1    2    3
## [4,]    3    2    1    0    1    4
## [5,]    4    3    2    1    0    1
## [6,]    1    2    3    4    1    0

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    2    3    4    1
## [2,]    1    0    1    2    3    2
## [3,]    2    1    0    1    2    3
## [4,]    3    2    1    0    1    2
## [5,]    4    3    2    1    0    1
## [6,]    1    2    3    2    1    0

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    2    3    2    1
## [2,]    1    0    1    2    3    2
## [3,]    2    1    0    1    2    3
## [4,]    3    2    1    0    1    2
## [5,]    2    3    2    1    0    1
## [6,]    1    2    3    2    1    0

Block APSP

n <- 24
blocksize <- 8
a <- circle_graph(n)
plotg(a)

it <- 0
for (it in 1:3) {
  
  inds <- (blocksize * (it-1) + 1):(blocksize * it)
  a_new <- a
  a_new[inds, inds] <- fw(a[inds, inds, drop = FALSE])
  plotg(a, inds = inds)
  plotl(a, a_new)
  a <- a_new
  title(paste("Iteration", it, "a"))
  
  a_new[inds, ] <- minplus(a[inds, inds, drop = FALSE], a[inds, , drop = FALSE],
                         a[inds, , drop = FALSE])
  a_new[, inds] <- minplus(a[, inds, drop = FALSE], a[inds, inds, drop = FALSE],
                           a[, inds, drop = FALSE])
  plotg(a, inds = inds)
  plotl(a, a_new, inds = inds)
  title(paste("Iteration", it, "b"))
  a <- a_new
  
  a_new <- minplus(a[, inds, drop = FALSE], a[inds, , drop = FALSE], a)
  plotg(a, inds = inds)
  plotl(a, a_new, inds = inds)
  title(paste("Iteration", it, "c"))
  a <- a_new
  
  
}